#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "huffman.h"

extern int MAXLENGTH;
extern int CODELENGTH;
extern int MAXLINE;

eTable *lookup_table;
int pointer;
charTable *cTable;

int noOfChars;

void printHuffmanCodes(const huffmanTree * t){
// prints out the codes contained in a Huffman Tree
// uses auxiliary printHuffmanCodesAux
    char code [16];
	//printf("Number of chars = %d\n", noOfChars);
	lookup_table = (eTable *) malloc (noOfChars * sizeof(eTable));
	if (lookup_table == NULL){
		perror("Memory error!");
		exit(0);
	}
	pointer = 0;
    char * code_ptr = code;
    printHuffmanCodesAux(t, code_ptr, code);
}

void copyValues(char *code){
	int length = strlen(code) +1;
	int i;
	for (i = 0; i < length; i++){
		lookup_table[pointer].value[i] = code[i];
	}
}

void printHuffmanCodesAux(const huffmanTree * t, char * code_ptr, char * code){
// Given Huffman Tree and codes (array of char) and a pointer into codes code_ptr
// function prints out all the Huffman codes contained in the Huffman Tree
    if (t->left == NULL && t->right == NULL){
		lookup_table[pointer].letter = t->letter; 
		copyValues(code);
		//printf("Character %c has code %s \n", t->letter, code);
		pointer++;
    }else if (t->left != NULL){
        * code_ptr = '0';
        code_ptr++;
        * code_ptr = '\0';
        printHuffmanCodesAux(t->left, code_ptr, code);
        code_ptr--;
    }
	if (t->right != NULL){
        * code_ptr = '1';
        code_ptr++;
        * code_ptr = '\0';
        printHuffmanCodesAux(t->right, code_ptr, code);
        code_ptr--;
    }
}

void printHuffmanTree(const huffmanTree * t, int level, char type){
// Prints out the contents of a Huffman Tree 
    int count;
    if(level==0) printf("-HuffmanTree:\n");
    for(count=0; count <= level; count++) printf("  "); printf("->(%c) ",type); 
    if (t->left == NULL && t->right == NULL){
        printf("Leaf: '%c' has count %d\n", t->letter, t->count);
         return;
    }
    printf("Node has count %d\n", t->count);
    if (t->left !=NULL){
        printHuffmanTree(t->left,level+1,'L');
    }
    if (t->right !=NULL){
        printHuffmanTree(t->right,level+1,'R');
    }
}

void printHuffmanTreeList(huffmanTreeList * list_ptr){
    // Prints out a list of Huffman Trres
    while (list_ptr != NULL){
        printf("HuffmanTreeList : \n");
        printHuffmanTree(list_ptr->huffman,0,'T');
        list_ptr = list_ptr->next;
    }
    printf("\n");
}

void freeHuffmanTree(huffmanTree * t){
// deallocates memory for a huffman tree
	if(t==NULL) return;
	freeHuffmanTree(t->left);
	freeHuffmanTree(t->right);
	free(t);
}

void freeHuffmanTreeList(huffmanTreeList * l){
// deallocates memory for a list of huffman trees
	if(l==NULL) return;
	freeHuffmanTreeList(l->next);
	freeHuffmanTree(l->huffman);
	free(l);
}

//Returns the number of time the character c appears in the string text.
int numChars(char * text, char c){
	int length = strlen(text);
	int count = 0, i;
	for(i = 0; i < length ; i++){
		if (text[i] == c)
		count++;
	}
	return count;
}

//Checks whether the character c is present in letters.
int present (char * letters, char c ){
	while(*letters != '\0'){
		if (*letters == c)
			return 1;
			letters++;
		}       
	return 0;
}

huffmanTreeList *  addToHuffmanTreeList(huffmanTreeList * list, huffmanTree * t){
	if (list == NULL || t-> count < list-> huffman-> count){             
		struct _huffmanTreeList *treeList = (struct _huffmanTreeList *) malloc (sizeof(struct _huffmanTreeList));
		if (treeList == NULL){
			perror("Memory Error");
			return NULL;
		}
		treeList->huffman = t;
		treeList->next = list;
		return treeList;
	}else{
		list->next = addToHuffmanTreeList(list->next, t);
		return list;
	}
}

huffmanTreeList * makeHuffmanTreeList (char * text, char * lookUp){
	int length = strlen(lookUp);
	cTable = (charTable *) malloc (noOfChars * sizeof(charTable));
	if (cTable == NULL){
		perror("Memory Error!");
		exit(0);	
	}
    int i;
    struct _huffmanTreeList *treeList = NULL;
    for(i = 0; i < length; i++){
		char c = lookUp[i];
		int count = numChars(text, c);
		cTable[i].letter=c;
		cTable[i].count=count;
		huffmanTree *tree = (huffmanTree *) malloc (sizeof(huffmanTree));
		tree->count = count;
		tree->letter = c;
		//printf("Character %c has count %d\n", c, count);
		tree->left= NULL;
		tree->right = NULL;
		treeList = addToHuffmanTreeList(treeList, tree);
	}
	return treeList;
}



huffmanTreeList *  reduceHuffmanTreeList(huffmanTreeList * huffmanList){
	while(huffmanList ->next != NULL){
    	struct _huffmanTree *treeA = huffmanList->huffman;
        huffmanList = huffmanList->next;
        struct _huffmanTree *treeB = huffmanList->huffman;
        huffmanList = huffmanList->next;
        struct _huffmanTree *newTree = (struct _huffmanTree *) malloc (1 * sizeof (struct _huffmanTree));
		if (newTree == NULL){
			perror("Memory error");
			return NULL;
		}
		newTree-> left = treeA;
        newTree->right = treeB;
        newTree->count = (treeA->count) + (treeB->count);
        huffmanList = addToHuffmanTreeList(huffmanList, newTree);
	}
	return huffmanList;
}

char * removeDuplicates(char * text){
        int length = strlen(text);
        char *newString = (char *) malloc (length * sizeof(char));
        if (newString == NULL){
                perror("Memory error!");
                return NULL;
        }
        int i, j = 0;
        for (i = 0; i < length; i++){
                if (!present (newString, text[i])){
                        newString[j] = text[i];
                        j++;
                        newString[j] = '\0';
                }
        }
		noOfChars = strlen(newString);
        return newString;
}

void append(char *string, char c){
	int len = strlen(string);
	string[len] = c;
	string[len+1] = '\0';
}


char * decode(char * code_ptr, huffmanTree * huffman){
	huffmanTree *original = huffman;
	char string[MAXLINE*MAXLENGTH];
	while (*code_ptr != '\0' ){
		if (*code_ptr == '0'){
			if (huffman->left == NULL){
				append(string, huffman->letter);
				huffman = original;
			}else{
				code_ptr++;
				huffman = huffman->left;
			}
		}else if (*code_ptr == '1'){
			if (huffman->right == NULL){
				append(string, huffman->letter);
				huffman = original;
			}else{
				code_ptr++;
				huffman = huffman->right;
			}				
		}
	}
	strcat(string, &huffman->letter);
	int len = strlen(string) + 1;
	char *result = (char *) malloc (len);
	if (result == NULL){
		perror ("Memory error");
		exit(0);
	}
	result = strcpy(result,string);
	return result;
}

char *  encode (char * text, huffmanTree * huffman){
	char result[CODELENGTH*MAXLINE];
	result[0]='\0';
	while(*text != '\0'){
		int i;
		for (i = 0; i < noOfChars; i++){
			if (*text == lookup_table[i].letter){
				strcat(result,lookup_table[i].value);	
				break;
			}
		}
		text++;		
	}
	int length = strlen(result) + 1;	
	char *r = (char *) malloc (length * sizeof(char));
	r[length] = '\0';
	if (r == NULL){
		perror("Memory Error!");
		exit(0);
	}
	r = strcpy(r,result);
	return r;
}
